Most interesting combinatorial optimization problems are hard to solve. To name a few, the maximum common subgraph, graph partitioning, graph colouring, and travelling salesman problems are among those combinatorial optimization problems which have been proved to be NP-hard. Some of these problems have significant real-world applications which make them especially interesting. For example, the minimum dominating set problem is an interesting problem used in the analysis of social networks.
A social network can be interpreted as a graph of relationships and interactions between a set of people. Nodes of a social network can represent individuals and organizations, and two nodes are adjacent if there is some kind of relationship between them.
Finding the minimum number of people in a social network which are familiar to the whole set of individuals is an interesting problem. This is because we can interpret these people as being the most influential individuals in the network. Finding the most influential individuals in the network can be done by solving an instance of the minimum dominating set problem for the graph representing the social network.
An interesting example of a social network is a web graph. A web graph is defined as a directed graph whose nodes are the pages of the World Wide Web, and there is a directed edge between, say webpage X to webpage Y, if there is a hyperlink on page X referring to page Y.
A variant of the minimum dominating set problem is the minimum connected dominating set problem. Aside from its application in the study of social networks, this problem can be used in designing mobile ad-hoc networks.
A mobile ad-hoc network is a self-configuring wireless network of mobile devices which are connected without wires and over an infrastructure-less network, i.e., there is no central administration in the network.
Usually, each node in a wireless network is a computing device with a limited energy source such as a battery. The energy consumed for transmitting a message increases super-linearly with transmission distance.
Fortunately, extending the idea of constructing a backbone-like structure in conventional wired networks, such as the Internet, to wireless networks through the notion of a virtual backbone is quite feasible.
Exploiting a virtual backbone has important immediate benefits. By incorporating only the nodes forming the backbone in the routing procedures, the telecommunications overhead is reduced, the bandwidth efficiency is increased, and the overall energy consumption is decreased. This advantage becomes more pronounced as the size of the backbone becomes smaller. Hence, people are motivated to find the smallest-sized possible virtual backbone.
Another real-world example of an application of the minimum connected dominating set problem is in the development of optical telecommunications networks due in part to exponentially growing demands of users.
One of the main problems that these networks must overcome is the deterioration of the optical signal as the distance from the source increases. Therefore, signals must be regenerated periodically using regenerators. In practice, the network is designed so that regenerators are placed at nodes of the network in a way such that all nodes of the network can communicate without significant signal impairments.
One can see that designing a smallest-sized virtual backbone as well as finding the minimum number of regenerators in an optical telecommunications network is a matter of solving a minimum connected dominating set problem.
Features of the invention will be apparent from review of the disclosure, drawings, and description of the invention below.